package easy.demo01;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: wfmiss
 * @Date: 2023/12/11/10:56
 * @Description:
 * 题目来源：力扣 https://leetcode.cn/problems/longest-common-prefix/
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 示例 1：
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 */
public class Solution {
    public static void main(String[] args) {
        /**
         * 测试用例：
         * 输入：strs = ["caa","","a","acb"]
         * 输出：""
         *
         * 输入：strs = ["a"]
         * 输出："a"
         *
         * 输入：strs = ["flower","flow","flight"]
         * 输出："fl"
         *
         * 输入：strs = ["dog","racecar","car"]
         * 输出：""
         */

        System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
    }

    /**
     * 优质解法 1
     * @param strs
     * @return
     */

    public static String longestCommonPrefix(String[] strs) {
        String strMin=strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(strMin)!=0){
                strMin=strMin.substring(0,strMin.length()-1);
                if (strMin.isEmpty()){
                    return "";
                }
            }
        }
        return strMin;
    }

    /**
     * 解法 2
     * 运行慢，
     * @param strs
     * @return
     */
    public static String longestCommonPrefix1(String[] strs) {
        // 如果只有一个字符串，则直接返回
        if (strs.length == 1 ) return strs[0];
        char str;
        String s = "", strMin = strs[0];
        // 找出长度最短的字符串
        for ( int i = 1; i < strs.length; i++) {
            strMin = strMin.length() < strs[i].length() ? strMin : strs[i];
        }
        // 如果最短的字符串为"",则直接返回
        if (strMin == "") return strMin;
        for (int i = 0; i < strMin.length(); i++) {
            // 依次取出最短字符串的字符
            str = strMin.charAt(i);
            // str循环与每个字符串的相同位字符比较是否一致
            for (int j = 0; j < strs.length; j++) {
                // 如果不一致则直接返回s里存储的已经比较过的字符
                if (str != strs[j].charAt(i)) return s;
            }
            // 把比较过的字符积攒给s
            s += str;
        }
        // 所有字符串均为一致
        return s;
    }
}
